package com.future;

/**
 * Description: 188. ������Ʊ�����ʱ�� IV (��ˢ��15)
 * ����һ����������?prices �����ĵ� i ��Ԫ��?prices[i] ��һ֧�����Ĺ�Ʊ�ڵ� i ��ļ۸�
 * <p>
 * ���һ���㷨�����������ܻ�ȡ�������������������� k �ʽ��ס�
 * <p>
 * ע�⣺�㲻��ͬʱ�����ʽ��ף���������ٴι���ǰ���۵�֮ǰ�Ĺ�Ʊ����
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺k = 2, prices = [2,4,1]
 * �����2
 * ���ͣ��ڵ� 1 �� (��Ʊ�۸� = 2) ��ʱ�����룬�ڵ� 2 �� (��Ʊ�۸� = 4) ��ʱ����������ʽ������ܻ������ = 4-2 = 2 ��
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/7 09:49
 */
public class Solution_188 {

    public static void main(String[] args) {
        int[] prices = {3, 2, 6, 5, 0, 3};
        prices = new int[]{3, 1, 2, 9, 2, 3, 6, 8};
        int k = 1;
        prices = new int[]{1, 2};
        k = 1;

        prices = new int[]{3, 3, 5, 0, 0, 3, 1, 4};
        k = 2;


        System.out.println(maxProfit(k, prices));
        System.out.println(maxProfit_v2(k, prices));
    }

    /**
     * eg:������⣬������͹���
     * ���㣺dp[5][3]
     * 1��dp[5][2]
     * 2��dp[4][2]+prices[5]-prices[4]
     * 3��dp[3][2]+prices[5]-prices[3]
     * 4��dp[2][2]+prices[5]-prices[2]
     * 5��dp[1][2]+prices[5]-prices[1]
     * 6��dp[0][2]+prices[5]-prices[0]
     * ���԰ѹ�����prices[5]������������£�
     * 1'��dp[5][2]
     * 2'��dp[4][2]-prices[4]
     * 3'��dp[3][2]-prices[3]
     * 4'��dp[2][2]-prices[2]
     * 5'��dp[1][2]-prices[1]
     * 6'��dp[0][2]-prices[0]
     * dp[5][3]ֵ��������1'��6'����е����ֵ+prices[5]
     * dp[6][3]
     * 1��dp[6][2]
     * 2��dp[5][2] +prices[6]-prices[5]
     * 3��dp[4][2]+prices[6]-prices[4]
     * 4��dp[3][2]+prices[6]-prices[3]
     * 5��dp[2][2]+prices[6]-prices[2]
     * 6��dp[1][2]+prices[6]-prices[1]
     * 7��dp[0][2]+prices[6]-prices[0]
     * ���԰ѹ�����prices[6]������������£�
     * 1'��dp[6][2]
     * 2'��dp[5][2] -prices[5]
     * 3'��dp[4][2]-prices[4]
     * 4'��dp[3][2]-prices[3]
     * 5'��dp[2][2]-prices[2]
     * 6'��dp[1][2]-prices[1]
     * 7'��dp[0][2]-prices[0]
     * <p>
     * dp[6][3]ֵ��������1'��7'����е����ֵ+prices[6]
     * dp[6][3]��dp[5][3]�����й����Ĳ���
     * 2'��dp[4][2]-prices[4]
     * 3'��dp[3][2]-prices[3]
     * 4'��dp[2][2]-prices[2]
     * 5'��dp[1][2]-prices[1]
     * 6'��dp[0][2]-prices[0]
     * ��ô���԰��ⲿ�ֵ����ֵ��¼��������������һ��ʱ��ֱ��ʹ�ã�����Ҫ���±�����
     *
     * @param k
     * @param prices
     * @return
     */
    public static int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0 || k <= 0) {
            return 0;
        }
        int N = prices.length;
        if (k >= N / 2) {
            return allSegment(prices);
        }
        int[][] dp = new int[N][k + 1];
        for (int col = 1; col < k + 1; col++) {
            /**
             * dp[1][col] :
             * 1��dp[0][col]
             * 2��dp[0][col-1]+[col]-[0]
             */
            dp[1][col] = Math.max(dp[1][col - 1], dp[0][col - 1] + prices[col] - prices[0]);
            int max = 0;
            for (int row = 1; row < N; row++) {
                for (int i = row - 1; i >= 0; i--) {
                    /**
                     * dp[i][j] ֵΪ������������ֵ
                     * 1��dp[i-1][j] ---������Ե����ó���
                     * 2��dp[i-1][j-1] + prices[i]-prices[i-1]
                     * 3��dp[i-2][j-1] + prices[i]-prices[i-2]
                     * 4��dp[i-3][j-1] + prices[i]-prices[i-3]
                     *  ...
                     *  dp[0][j-1] + prices[i]-prices[0]
                     *
                     */
                    max = Math.max(max, dp[i][col - 1] + prices[row] - prices[i]);
                }
                dp[row][col] = Math.max(max, dp[row - 1][col]);
            }
        }
        return dp[N - 1][k];
    }

    /**
     * ����
     *
     * @param k
     * @param prices
     * @return
     */
    public static int maxProfit_v2(int k, int[] prices) {
        if (prices == null || prices.length == 0 || k <= 0) {
            return 0;
        }
        int N = prices.length;
        if (k >= N / 2) {
            return allSegment(prices);
        }
        int[][] dp = new int[N][k + 1];
        for (int col = 1; col < k + 1; col++) {
            /**
             * dp[1][col] :
             * 1��dp[0][col]
             * 2��dp[0][col-1]+[col]-[0]
             */
            int preBest = dp[0][col - 1] - prices[0];
            dp[1][col] = Math.max(dp[1][col - 1], preBest + prices[col]);
            int max = 0;
            for (int row = 1; row < N; row++) {
                /**
                 * dp[i][j] ֵΪ������������ֵ
                 * 1��dp[i-1][j] ---������Ե����ó���
                 * 2��dp[i-1][j-1] + prices[i]-prices[i-1]
                 * ------------------------------------------
                 * 3��dp[i-2][j-1] + prices[i]-prices[i-2]
                 * 4��dp[i-3][j-1] + prices[i]-prices[i-3]
                 *  ...
                 *  dp[0][j-1] + prices[i]-prices[0]
                 *
                 * dp[i-1][j] ֵΪ������������ֵ
                 * 1��dp[i-2][j] ---������Ե����ó���
                 * 2��dp[i-2][j-1] + prices[i]-prices[i-2]
                 * 3��dp[i-3][j-1] + prices[i]-prices[i-3]
                 *  ...
                 *  dp[0][j-1] + prices[i]-prices[0]
                 *
                 */
                preBest = Math.max(preBest, dp[row - 1][col - 1] - prices[row - 1]);
                max = Math.max(max, preBest + prices[row]);
                dp[row][col] = Math.max(max, dp[row - 1][col]);
            }
        }
        return dp[N - 1][k];
    }

    private static int allSegment(int[] prices) {
        int maxProfit = 0;
        int N = prices.length;
        int minFragment = prices[0];
        int maxFragment = prices[0];
        int L = 1;
        while (L < N) {
            int val = prices[L];
            if (val < maxFragment) {
                maxProfit += (maxFragment - minFragment);
                minFragment = val;
            }
            maxFragment = val;
            L++;
        }
        if (maxFragment > minFragment) {
            maxProfit += (maxFragment - minFragment);
        }
        return maxProfit;
    }
}
